package com.jack.leetcode.每日一题;

import java.util.*;

/***
 * @author zhangjie
 * @date 2020/3/28 22:27
 */
public class 单词的压缩编码 {

    public static void main(String[] args) {
        String[] words = {"time", "me", "bell"};
        System.out.println(minimumLengthEncoding(words));
        String[] a = {"t"};
        System.out.println(minimumLengthEncoding(a));
        String[] b = {"me","time"};
        System.out.println(minimumLengthEncoding(b));
        String[] c = {"time","me"};
        System.out.println(minimumLengthEncoding(c));
    }

    public static int minimumLengthEncoding(String[] words) {
        Arrays.sort(words,(s1,s2)->s2.length()-s1.length());
        int result = 0;
        Trie trie = new Trie();
        for(int i=0;i<words.length;i++){
            result +=trie.insert(words[i]);
        }
        return result;
    }
}
class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public int insert(String word){
        TrieNode cur = root;
        boolean isNew = false;
        for(int i = word.length()-1;i>=0;i--){
            int c = word.charAt(i)-'a';
            if(cur.children[c]==null){
                isNew = true;
                cur.children[c] = new TrieNode();
            }
            cur = cur.children[c];
        }
        return isNew?word.length()+1:0;
    }

    class TrieNode{
        char val;
        TrieNode[] children = new TrieNode[26];
        public TrieNode(){}
    }
}
